// 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

// 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

// 示例: 

// 你可以将以下二叉树：

//     1
//    / \
//   2   3
//      / \
//     4   5

// 序列化为 "[1,2,3,null,null,4,5]"
// 提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

// 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。


#include <string>
#include <queue>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


 // 只要能序列化之后再反序列化回来即可，没有固定的形式
class Codec {
public:

    // Encodes a tree to a single string.
    // 层序遍历，使用队列
    string serialize(TreeNode* root) {
        string res{""};
        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            TreeNode* t = q.front();
            q.pop();
            if (t != nullptr) {
                res += to_string(t->val);
                res += ",";
                q.push(t->left); // 不需要判断是否为nullptr
                q.push(t->right);
            } else {
                res += "null,";
            }
        }
        return res; // 没有去除结尾的null
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> vals = split(data);
        queue<TreeNode*> q{};
        if (vals[0] == "null") return nullptr;
        q.push(new TreeNode(stoi(vals[0])));
        TreeNode *res = q.front();
        int n = vals.size();
        for(int i{1}; i < n;) { // 两两一组
            if (vals[i] != "null") {
                TreeNode* p = new TreeNode(stoi(vals[i]));
                q.push(p);
                q.front()->left = p;
            }
            ++i; // 不管是不是空，都加一
            if (vals[i] != "null") {
                TreeNode* p = new TreeNode(stoi(vals[i]));
                q.push(p);
                q.front()->right = p;
            }
            ++i;
            q.pop();
        }
        return res;
    }

private:
    // 按逗号分割字符串
    vector<string> split(const string& data) {
        int start{0};
        vector<string> res{};
        while(1) {
            auto end = data.find(',', start); // 从下标为start的位置开始找','，找到了就返回下标
            if (end == string::npos) break; // 找到最后
            res.push_back(data.substr(start, end - start));
            start = end + 1;
        }
        return move(res); // 移动res，而不是复制再返回
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));